struct DSU {
	DSU(int n) : siz_(n + 1), father_(n + 1), connected_blocks_(n) {
		for (int i = 1; i <= n; i++) {
			siz_[i] = 1;
			father_[i] = i;
		}
	}

	int find(int x) {
		return x == father_[x] ? x : father_[x] = find(father_[x]);
	} 

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	void merge(int x, int y) {
		if (same(x, y)) {
			return;
		}
		x = find(x), y = find(y);
		father_[y] = x;
		siz_[x] += siz_[y];
		connected_blocks_--;
	}

	int getBlocks() {
		return connected_blocks_;
	}

	int getVertex(int x) {
		return siz_[find(x)];
	}

	vector<int> siz_, father_;
	int connected_blocks_;
};